package org.chnxi.datastructures.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树
 */
public class HuffmanTreeDemo {

    public static void main(String[] args) {
        System.out.println("分布创建：");
        int[] arr = {13,7,8,3,29,6,1};
        createHuffmanTreeByStep(arr);
        System.out.println("==================================================");
        System.out.println("一次性创建：");
        int[] arr2 = {13,7,8,3,29,6,1};
        HTNode root = createHuffmanTree(arr2);
        System.out.println("树的根："+root);
        System.out.println("使用前序遍历：");
        printHuffmanTreeByPreOrder(root);
    }

    /**
     * 使用前序打印赫夫曼树的内容
     * @param root
     */
    public static void printHuffmanTreeByPreOrder(HTNode root){
        if(root != null){
            root.printPreOrder();
        }else{
            System.out.println("空树");
        }
    }

    /**
     * 创建赫夫曼树
     * @param arr 赫夫曼树的所有叶子节点
     * @return 创建后树的根节点
     */
    public static HTNode createHuffmanTree(int[] arr){
        List<HTNode> nodes = new ArrayList<HTNode>();
        for (int val : arr){
            HTNode htnode = new HTNode(val);
            nodes.add(htnode);
        }

        while (nodes.size() > 1){
            Collections.sort(nodes);

            HTNode left = nodes.get(0);
            HTNode right = nodes.get(1);

            HTNode parent = new HTNode(left.value + right.value);
            parent.left = left;
            parent.right = right;

            nodes.remove(parent.left);
            nodes.remove(parent.right);
            nodes.add(parent);
        }

        return nodes.get(0);
    }

    /**
     * 分布讲解
     * @param arr
     */
    public static void createHuffmanTreeByStep(int[] arr){
        //第一步：遍历arr数组，将arr每个元素构成一个个Node，将Node放入到List中
        List<HTNode> nodes = new ArrayList<HTNode>();
        for (int val : arr){
            HTNode htnode = new HTNode(val);
            nodes.add(htnode);
        }
        Collections.sort(nodes);
        System.out.println("排序后："+nodes);

        //第二步：取出权值最小的二叉树节点
        HTNode left = nodes.get(0);
        HTNode right = nodes.get(1);

        //第三步：构建一个新的二叉树
        HTNode parent = new HTNode(left.value + right.value);
        parent.left = left;
        parent.right = right;

        nodes.remove(parent.left);
        nodes.remove(parent.right);
        nodes.add(parent);

        System.out.println("第一轮处理后："+nodes);

        //…… 往后步骤循环
    }
}

/**
 * 为了让Node支持Collections集合排序，让Node实现Comparable
 */
class HTNode implements Comparable<HTNode> {
    int value; //节点权值
    HTNode left; //左子节点
    HTNode right; //右子节点

    public HTNode(int value){
        this.value = value;
    }

    @Override
    public String toString() {
        return "HTNode{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(HTNode o) {
        //从小到大排
        return this.value - o.value;
    }

    /**
     * 前序遍历打印
     */
    public void printPreOrder(){
        System.out.println(this);
        if(this.left != null){
            this.left.printPreOrder();
        }
        if(this.right != null){
            this.right.printPreOrder();
        }
    }
}
